package LeetCode.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
		Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
	
	You may assume the integer do not contain any leading zero, except the number 0 itself.
	
	The digits are stored such that the most significant digit is at the head of the list.
题目大意

	一个整数按位存储于一个int数组中，排列顺序为：最高位在array[0] ，最低位在[n-1]，例如：98，存储为：array[0]=9; array[1]=8;
	
解题思路
	
	从数组的最后一位开始加1，需要考虑进位，如果到[0]位之后仍然有进位存在，需要新开一个长度为(n.length + 1)的数组，拷贝原来的数组。
	
 * @Date 2017-09-17 14：42
 */
public class _066_Plus_One {
	
	/**
	 * @My:
	 * @param digits
	 * @return
	 */
    public int[] plusOne(int[] digits) {
    	//是否需要进位	0:不需要, 1:需要
    	int flag = 0;
    	int N = digits.length;
    	//遍历原数组(digits)
    	for (int i = N-1; i >= 0; i --) {
    		int sum = 0;
    		if (i == N-1) 	sum = digits[i] + 1 + flag;
    		else 			sum = digits[i] 	+ flag;
    		if (sum >= 10) {
    			digits[i] = sum % 10;
    			flag = 1;
    		} else {
    			digits[i] = sum;
    			flag = 0;
    		}
    	}
    	//flag==1需要进位，新开一个数组拷贝过去
    	if (flag == 1) {
    		int[] newDigits = new int[digits.length+1];
    		for (int i = N-1; i >= 0; i --) 
    			newDigits[i+1] = digits[i];
    		newDigits[0] = 1;
    		return newDigits;		//返回新数组
    	}
    	TraverseUtils.println(digits);
    	return digits;
    }

    
	public static void main(String[] args) {
		_066_Plus_One obj = new _066_Plus_One();
		obj.plusOne(new int[] {3,0});
	}

}
